import java.util.ArrayList;
import java.util.Scanner;

public class App {
    final static int MaxRandNumAbs = 100;

    public static void main(String[] args) throws Exception {
        // 控制台输入测试数组大小，生成随机数组测试
        // test1为平均时间测试，test2为最坏情况测试
        Scanner cin = new Scanner(System.in);
        int size = cin.nextInt();
        ArrayList<Test> test1 = new ArrayList<>(size), test2 = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            Test current = new Test();
            current.index = i;
            current.value = (int) ((Math.random() - 0.5) * 2 * MaxRandNumAbs);
            test1.add(current);
        }
        for (int i = 0; i < size; i++) {
            Test current = new Test(i, size - i);
            test2.add(current);
        }
        long startTime = System.currentTimeMillis();
        QuickSort.quicksort(test1, 0, size - 1);
        long endTime1 = System.currentTimeMillis();
        QuickSort.quicksort(test2, 0, size - 1);
        long endTime2 = System.currentTimeMillis();
        MaxHeap mh = new MaxHeap();
        test1 = mh.heapSort(test1);
        long endTime3 = System.currentTimeMillis();
        MergeSort.mergesort(test1);
        long endTime4 = System.currentTimeMillis();
        System.out.println("快排平均运行时间：" + (endTime1 - startTime) + "ms" + "\n");
        System.out.println("快排最坏运行时间：" + (endTime2 - endTime1) + "ms" + "\n");
        System.out.println("堆排平均运行时间：" + (endTime3 - endTime2) + "ms" + "\n");
        System.out.println("归并排序运行时间：" + (endTime4 - endTime3) + "ms" + "\n");
        System.out.println(test1.toString());
        System.out.println(test2.toString());
        cin.close();
    }
}

class Test implements Comparable<Test> {
    int index;
    int value;

    public Test() {
    }

    public Test(int index, int value) {
        this.index = index;
        this.value = value;
    }

    @Override
    public int compareTo(Test o) {
        if (this.value > o.value)
            return 1;
        else if (this.value < o.value)
            return -1;
        else
            return 0;
    }

    @Override
    public String toString() {
        return "index=" + index + ", value=" + value + "\n";
    }
}

class MaxHeap<T extends Comparable<T>> extends ArrayList<T> {
    public void MaxHeapIFY(int i) {
        // 以下标为i这个节点为根节点的小二叉树不满足最大堆的要求，调整最大堆
        int current = i;
        while (current != -1) {
            int left = this.getLeft(current), right = this.getRight(current);
            if (left > this.size() - 1)
                return;
            if ((left == this.size() - 1)
                    || ((this.get(left).compareTo(this.get(current)) > 0)
                            && (this.get(left).compareTo(this.get(right)) > 0))) {
                T a = this.get(current);
                this.set(current, this.get(left));
                this.set(left, a);
                current = left;
            } else if (this.get(right).compareTo(this.get(current)) > 0) {
                T a = this.get(current);
                this.set(current, this.get(right));
                this.set(right, a);
                current = right;
            } else {
                current = -1;
            }
        }
        return;
    }

    public void buildMaxHeap() {
        // 初始化一个最大堆
        int size = this.size();
        for (int i = getParent(size - 1); i >= 0; i--) {
            this.MaxHeapIFY(i);
        }
        return;
    }

    public void insert(T a) {
        // 向堆中插入一个数
        this.add(a);
        int size = this.size();
        for (int i = size - 1; i > 0; i = this.getParent(i)) {
            int parent = this.getParent(i);
            if (this.get(parent).compareTo(this.get(i)) < 0) {
                T b = this.get(parent);
                this.set(parent, this.get(i));
                this.set(parent, b);
            } else
                break;
        }
    }

    public ArrayList<T> heapSort(ArrayList<T> array) {
        // 利用最大堆进行排序
        for (int i = 0; i <= array.size() - 1; i++)
            this.add(array.get(i));
        ArrayList<T> answer = new ArrayList<T>();
        this.buildMaxHeap();
        int size = this.size();
        for (int i = size - 1; i >= 0; i--) {
            T a = this.get(0);
            this.set(0, this.get(i));
            this.set(i, a);
            answer.add(0, this.remove(i));
            this.MaxHeapIFY(0);
        }
        return answer;
    }

    public int getLeft(int i) {
        // 给定一个下标，计算出其父节点，左右孩子节点的下标
        return i * 2 + 1;
    }

    public int getRight(int i) {
        return i * 2 + 2;
    }

    public int getParent(int i) {
        return (i - 1) / 2;
    }
}

class QuickSort {
    public static <T extends Comparable<T>> void quicksort(ArrayList<T> array, int p, int r) {
        int a, r2, p2;
        while (true) {
            a = partition(array, p, r);
            if (a == -1)
                break;
            r2 = r;
            r = a - 1;
            p2 = a + 1;
            quicksort(array, p2, r2);
        }
    }

    private static <T extends Comparable<T>> int partition(ArrayList<T> array, int p, int r) {
        if (p >= r)
            return -1;
        T x = array.get(r);
        int i = p;
        ArrayList<T> c = new ArrayList<>(r - p + 1);
        for (int a = p; a <= r; a++) {
            T current = array.get(a);
            if (current.compareTo(x) <= 0) {
                array.set(a, array.get(i));
                array.set(i, current);
                i++;
            } else
                c.add(current);
        }
        for (int a = i; a <= r; a++)
            array.set(a, c.get(a - i));
        return i - 1;
    }
}

class MergeSort {
    public static <T extends Comparable<T>> void mergesort(ArrayList<T> array) {
        int size = array.size(), a = 1;
        while (a < size) {
            for (int i = 0; i <= size - a; i = i + 2 * a) {
                int r = i + 2 * a - 1;
                if (r >= size)
                    r = size - 1;
                merge(array, i, i + a, r);
            }
            a = a * 2;
        }
    }

    private static <T extends Comparable<T>> void merge(ArrayList<T> array, int p1, int p2, int r) {
        ArrayList<T> ac = new ArrayList<>();
        int i1 = p1, i2 = p2;
        for (int i = 0; i <= r - p1; i++) {
            if (i2 > r || (i1 < p2 && array.get(i1).compareTo(array.get(i2)) <= 0)) {
                ac.add(i, array.get(i1));
                i1++;
            } else {
                ac.add(i, array.get(i2));
                i2++;
            }
        }
        for (int i = 0; i <= r - p1; i++)
            array.set(i + p1, ac.get(i));
    }
}